//
// Created by francklinson on 2021/8/3 AT 0:05.
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int findUnsortedSubarray(vector<int> &nums) {
        // 排序
        if (is_sorted(nums.begin(), nums.end()))
            return 0;
        vector<int> sorted_num(nums);
        sort(sorted_num.begin(), sorted_num.end());
        int left = 0;
        while (sorted_num[left] == nums[left])
            ++left;
        int right = (int) nums.size() - 1;
        while (sorted_num[right] == nums[right])
            --right;
        return right - left + 1;
    }
};

class Solution2 { // 一次遍历
public:
    int findUnsortedSubarray(vector<int> &nums) {
        int n = nums.size();
        int maxn = INT_MIN, right = -1;
        int minn = INT_MAX, left = -1;
        for (int i = 0; i < n; i++) {
            if (maxn > nums[i]) {
                right = i;
            } else {
                maxn = nums[i];
            }
            if (minn < nums[n - i - 1]) {
                left = n - i - 1;
            } else {
                minn = nums[n - i - 1];
            }
        }
        return right == -1 ? 0 : right - left + 1;
    }
};

int main() {
    vector<int> nums{2, 6, 4, 8, 10, 9, 15};
    Solution2 solution;
    cout << solution.findUnsortedSubarray(nums) << endl;
    return 0;
}

